#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    bool isprime(int a, int b)
    {
        if (a == 1 || b == 1)
            return true;
        while (1)
        {
            int t = a % b;
            if (t == 0)
                break;
            else
            {
                a = b;
                b = t;
            }
        }
        if (b > 1) return false;
        else return true;
    }

    int countBeautifulPairs(vector<int>& nums)
    {
        int count = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            int ti = nums[i];
            while (ti > 9)
                ti /= 10;
            for (int j = i + 1; j < nums.size(); j++)
            {
                int tj = nums[j];
                tj = tj > 9 ? tj % 10 : tj;
                if (isprime(ti, tj))
                    count++;
            }
        }
        return count;
    }
};